#include "fifo.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/**
 * 函数：模拟FIFO（先进先出）页面置换算法。
 *
 * @param queue_frames 一个字符串，表示页面访问序列。
 *                     字符串中的每个字符是一个数字，表示一个页面号。
 * @param num_frames   页框的数量，表示物理内存中可用的页框数。
 */

static struct queue {
  int *data;
  int size;
  int front;
  int end;
  int capacity;
} *que; // 注意此时声明的全局que指针并为得到一个正确的存储queue类型的空间

void create_queue(int capacity) {
  que = (struct queue*)malloc(sizeof(struct queue));
  que -> capacity = capacity;
  que -> data = (int*)malloc(capacity * sizeof(int));
  memset(que -> data, -1, capacity * sizeof(int));
  que -> front = que -> end = -1;
  que -> size = 0;
}

void insert_queue(int num) {
  if (que -> size == que -> capacity) return;
  int end = que -> end;
  end = (end + 1) % que -> capacity;
  que -> end = end;
  que -> data[end] = num;
  que -> size++;
  return;
}

void pop_queue() {
  if(que -> size == 0) return;
  que -> front = (que -> front + 1) % que -> capacity;
  que -> size--;
  return;
}

int exist_elem(int num) {
  for (int i = que -> front; i != que -> end; i = (i + 1) % que -> capacity) {
    int j = (i + 1) % que -> capacity;
    if (que -> data[j] == num) return 1;
  }
  return 0;
}

void print_queue(int num) {
  printf("Access:%d,Frames: [", num);
  for (int i = 0; i < que -> capacity; i++) {
    printf("%d", que -> data[i]);
    if(i != que -> capacity - 1) printf(",");
  }
  printf("]\n");
}

void
fifo_page_replacement (char *queue_frames, int num)
{
  // TODO
  create_queue(num);
  char *token = strtok(queue_frames, ",");
  while(token != NULL) {
    int n = atoi(token);
    if(!exist_elem(n)) {
      if(que -> size == que -> capacity) {
        pop_queue();
      }
      insert_queue(n);
    }
    print_queue(n);
    token = strtok(NULL, ",");
  }
  free(que -> data);
  free(que);
}
